{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Invalid Parentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeInvalidParentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除无效的括号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由若干括号和字母组成的字符串 <code>s</code> ，删除最小数量的无效括号，使得输入的字符串有效。</p>\n",
    "\n",
    "<p>返回所有可能的结果。答案可以按 <strong>任意顺序</strong> 返回。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"()())()\"\n",
    "<strong>输出：</strong>[\"(())()\",\"()()()\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"(a)())()\"\n",
    "<strong>输出：</strong>[\"(a())()\",\"(a)()()\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \")(\"\n",
    "<strong>输出：</strong>[\"\"]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length <= 25</code></li>\n",
    "\t<li><code>s</code> 由小写英文字母以及括号 <code>'('</code> 和 <code>')'</code> 组成</li>\n",
    "\t<li><code>s</code> 中至多含 <code>20</code> 个括号</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-invalid-parentheses](https://leetcode.cn/problems/remove-invalid-parentheses/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-invalid-parentheses](https://leetcode.cn/problems/remove-invalid-parentheses/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"()())()\"', '\"(a)())()\"', '\")(\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        min_rm = float('inf')\n",
    "        ans = set()\n",
    "        vis = set()\n",
    "        \n",
    "        q = deque([(0, \"\", 0, 0)])\n",
    "        \n",
    "        while q:\n",
    "            idx, cur, ops, rm = q.popleft()\n",
    "            if idx == len(s):\n",
    "                if not ops:\n",
    "                    if rm < min_rm:\n",
    "                        min_rm = rm\n",
    "                        ans = {cur}\n",
    "                    elif rm == min_rm:\n",
    "                        ans.add(cur)\n",
    "                continue\n",
    "            if (idx, cur) in vis: continue\n",
    "            vis.add((idx, cur))\n",
    "            if s[idx] == '(':\n",
    "                q.append((idx+1, cur+'(', ops+1, rm))\n",
    "                q.append((idx+1, cur, ops, rm+1))\n",
    "            elif s[idx] == ')':\n",
    "                q.append((idx+1, cur, ops, rm+1))\n",
    "                if ops:\n",
    "                    q.append((idx+1, cur+')', ops-1, rm))\n",
    "            else:\n",
    "                q.append((idx+1, cur+s[idx], ops, rm))\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author:             何睿\n",
    "# @Create Date:        2019-02-10 15:47:49\n",
    "# @Last Modified by:   何睿\n",
    "# @Last Modified time: 2019-02-10 17:56:24\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: 'str') -> 'List[str]':\n",
    "        # 如果为空，返回空字符串\n",
    "        if not s: return [\"\"]\n",
    "        # 统计非法的左右括号的个数\n",
    "        left, right = 0, 0\n",
    "        for _s in s:\n",
    "            # 如果是左括号，left自增一次\n",
    "            if _s == \"(\": left += 1\n",
    "            # 如果没有非法的左括号，并且当前是右括号，right自增一次\n",
    "            if left == 0 and _s == \")\":\n",
    "                right += 1\n",
    "            # 否则如果当前是右括号，我们让当前的右括号和一个左括号匹配\n",
    "            # left自减一次\n",
    "            elif _s == \")\":\n",
    "                left -= 1\n",
    "        res = []\n",
    "        self.__dfs(s, 0, left, right, res)\n",
    "        return res\n",
    "\n",
    "    def __dfs(self, s, start, left, right, res):\n",
    "        # 递归结束条件\n",
    "        if not left and not right and self.__valid(s):\n",
    "            res.append(s)\n",
    "            return\n",
    "        for i in range(start, len(s)):\n",
    "            # 避免重复\n",
    "            if i != start and s[i] == s[i - 1]: continue\n",
    "            if s[i] == \"(\" or s[i] == \")\":\n",
    "                # 删除字符\n",
    "                current = s[0:i] + s[i + 1:]\n",
    "                if right > 0: self.__dfs(current, i, left, right - 1, res)\n",
    "                elif left > 0: self.__dfs(current, i, left - 1, right, res)\n",
    "\n",
    "        return\n",
    "\n",
    "    def __valid(self, s):\n",
    "        # 统计有效的括号个数\n",
    "        # 只要不到最后一个位置，左括号个数一定大于右括号的个数\n",
    "        # 最后一个位置左右括号的个数相等\n",
    "        count = 0\n",
    "        for _s in s:\n",
    "            # 遇到左括号，count加一\n",
    "            if _s == \"(\": count += 1\n",
    "            # 遇到右括号，count减一\n",
    "            if _s == \")\": count -= 1\n",
    "            # 如果count小于0，说明当前位置一定没有足够的左括号\n",
    "            # 和右括号进行匹配，返回False\n",
    "            if count < 0: return False\n",
    "        return count == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#coding=gbk\n",
    "#Remove Invalid Parentheses\n",
    "from collections import deque\n",
    "class Solution:\n",
    "\tdef removeInvalidParentheses(self, s):\n",
    "\t\t#dfs解法,最暴力解法\n",
    "\t\tset1=set()\n",
    "\t\tif self.isvalid(s):return [s]\n",
    "\t\tQ1={s}\n",
    "\t\tre=[]\n",
    "\t\twhile Q1:\n",
    "\t\t\tQ2=set()\n",
    "\t\t\tis_break=False\n",
    "\t\t\tfor s1 in Q1:\n",
    "\t\t\t\tfor index in range(len(s1)):\n",
    "\t\t\t\t\tt=s1[:index]+s1[index+1:]\n",
    "\t\t\t\t\tif s1[index] in '()' and t not in Q2:\n",
    "\t\t\t\t\t\tif self.isvalid(t):\n",
    "\t\t\t\t\t\t\tre.append(t)\n",
    "\t\t\t\t\t\t\tis_break=True\n",
    "\t\t\t\t\t\tQ2.add(t)\n",
    "\t\t\tif is_break:break\n",
    "\t\t\tQ1=Q2\n",
    "\t\treturn re\n",
    "\tdef isvalid(self,s):\n",
    "\t\tc=0\n",
    "\t\tfor x in s:\n",
    "\t\t\tif x=='(':\n",
    "\t\t\t\tc+=1\n",
    "\t\t\telif x==')':\n",
    "\t\t\t\tif c==0:return False\n",
    "\t\t\t\tc-=1\n",
    "\t\treturn c==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        def dfs(s):\n",
    "            mi = calc(s)\n",
    "            if mi == 0:\n",
    "                return [s]\n",
    "            ans = []\n",
    "            for x in range(len(s)):\n",
    "                if s[x] in ('(', ')'):\n",
    "                    ns = s[:x] + s[x+1:]\n",
    "                    if ns not in visited and calc(ns) < mi:\n",
    "                        visited.add(ns)\n",
    "                        ans.extend(dfs(ns))\n",
    "            return ans    \n",
    "        def calc(s):\n",
    "            a = b = 0\n",
    "            for c in s:\n",
    "                a += {'(' : 1, ')' : -1}.get(c, 0)\n",
    "                b += a < 0\n",
    "                a = max(a, 0)\n",
    "            return a + b\n",
    "\n",
    "        visited = set([s])    \n",
    "        return dfs(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: 'str') -> 'List[str]':\n",
    "        def dfs(s):\n",
    "            mi = calc(s)\n",
    "            if mi == 0:\n",
    "                return [s]\n",
    "            ans = []\n",
    "            for x in range(len(s)):\n",
    "                if s[x] in ('(', ')'):\n",
    "                    ns = s[:x] + s[x+1:]\n",
    "                    if ns not in visited and calc(ns) < mi:\n",
    "                        visited.add(ns)\n",
    "                        ans.extend(dfs(ns))\n",
    "            return ans    \n",
    "        def calc(s):\n",
    "            a = b = 0\n",
    "            for c in s:\n",
    "                a += {'(' : 1, ')' : -1}.get(c, 0)\n",
    "                b += a < 0\n",
    "                a = max(a, 0)\n",
    "            return a + b\n",
    "\n",
    "        visited = set([s])    \n",
    "        return dfs(s)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        def dfs(s):\n",
    "            mi = calc(s)\n",
    "            if mi == 0:\n",
    "                return [s]\n",
    "            ans = []\n",
    "            for x in range(len(s)):\n",
    "                if s[x] in ('(', ')'):\n",
    "                    ns = s[:x] + s[x+1:]\n",
    "                    if ns not in visited and calc(ns) < mi:\n",
    "                        visited.add(ns)\n",
    "                        print(ans)\n",
    "                        ans.extend(dfs(ns))\n",
    "            return ans    \n",
    "        def calc(s):\n",
    "            a = b = 0\n",
    "            for c in s:\n",
    "                a += {'(' : 1, ')' : -1}.get(c, 0)\n",
    "                b += a < 0\n",
    "                a = max(a, 0)\n",
    "            return a + b\n",
    "\n",
    "        visited = set([s])    \n",
    "        return dfs(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "  def removeInvalidParentheses(self, s):\n",
    "    \"\"\"\n",
    "    :type s: str\n",
    "    :rtype: List[str]\n",
    "    \"\"\"\n",
    "\n",
    "    def isValid(s):\n",
    "      stack = []\n",
    "      for c in s:\n",
    "        if c == \"(\":\n",
    "          stack.append(\"(\")\n",
    "        elif c == \")\":\n",
    "          stack.append(\")\")\n",
    "          if len(stack) >= 2 and stack[-2] + stack[-1] == \"()\":\n",
    "            stack.pop()\n",
    "            stack.pop()\n",
    "      return len(stack)\n",
    "\n",
    "    def dfs(s, res, cache, length):\n",
    "      if s in cache:\n",
    "        return\n",
    "\n",
    "      if len(s) == length:\n",
    "        if isValid(s) == 0:\n",
    "          res.append(s)\n",
    "          return\n",
    "\n",
    "      for i in range(0, len(s)):\n",
    "        if s[i] == \"(\" or s[i] == \")\" and len(s) - 1 >= length:\n",
    "          dfs(s[:i] + s[i + 1:], res, cache, length)\n",
    "          cache.add(s[:i] + s[i + 1:])\n",
    "\n",
    "    prepLeft = \"\"\n",
    "    for i in range(0, len(s)):\n",
    "      if s[i] == \"(\":\n",
    "        prepLeft += s[i:]\n",
    "        break\n",
    "      elif s[i] != \")\":\n",
    "        prepLeft += s[i]\n",
    "\n",
    "    prepRight = \"\"\n",
    "    for i in reversed(range(0, len(prepLeft))):\n",
    "      if prepLeft[i] == \")\":\n",
    "        prepRight += prepLeft[:i + 1][::-1]\n",
    "        break\n",
    "      elif prepLeft[i] != \"(\":\n",
    "        prepRight += prepLeft[i]\n",
    "\n",
    "    s = prepRight[::-1]\n",
    "    length = len(s) - isValid(s)\n",
    "    res = []\n",
    "    cache = set()\n",
    "    print(cache)\n",
    "    dfs(s, res, cache, length)\n",
    "    return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def removeInvalidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        if not s: return ['']\n",
    "        q, ans, vis = [s], [], set([s])\n",
    "        found = False\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            if self.isValidParentheses(cur):\n",
    "                found = True\n",
    "                #只要found变量变成True，说明在这一层已经能够移除最少的invalid括号达到剩下字符串是valid的目的了，所以不需要继续往下一层搜索，已经被加入到q中的子节点\n",
    "                ans.append(cur)\n",
    "            elif not found:\n",
    "                for i in range(len(cur)):\n",
    "                    if cur[i] == '(' or cur[i] == ')':\n",
    "                        t = cur[:i] + cur[i + 1:]\n",
    "                        if t not in vis:\n",
    "                            q.append(t)\n",
    "                            vis.add(t)\n",
    "        return ans\n",
    "\n",
    "    def isValidParentheses(self, s):#很好理解，多看看\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cnt += 1\n",
    "            elif c == ')':\n",
    "                if cnt == 0: return False\n",
    "                cnt -= 1\n",
    "        return cnt == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def helper(self, s: 'str', ans, lasti, lastj,left,right):\n",
    "        count=0\n",
    "        for index, char in enumerate(s):\n",
    "            if char == left:\n",
    "                count+=1\n",
    "            if char == right:\n",
    "                count-=1\n",
    "            if count >=0:\n",
    "                continue\n",
    "            for j in range(lastj,index+1):\n",
    "                if s[j] == right and (s[j-1]!=right or j == lastj):\n",
    "                    self.helper(s[:j]+s[j+1:],ans,index,j,left,right)\n",
    "            return\n",
    "        if left=='(':\n",
    "            self.helper(s[::-1],ans,0,0,')','(')\n",
    "        else:\n",
    "            ans.append(s[::-1])\n",
    "            \n",
    "    def removeInvalidParentheses(self, s: 'str') -> 'List[str]':\n",
    "        ans=[]\n",
    "        self.helper(s,ans,0,0,'(',')')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s):\n",
    "        l, r = 0, 0\n",
    "        self.res = []\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                l += 1\n",
    "            elif c == \")\":\n",
    "                if l == 0: \n",
    "                    r += 1\n",
    "                else:\n",
    "                    l -= 1\n",
    "\n",
    "        self.DFS(s, 0, l, r)\n",
    "        return self.res\n",
    "\n",
    "    def isValid(self, s):\n",
    "        count = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                count += 1\n",
    "            elif c == ')':\n",
    "                count -= 1\n",
    "            if count < 0: return False\n",
    "        return count == 0\n",
    "\n",
    "    def DFS(self, s, start, l, r):\n",
    "        if l == 0 and r == 0:\n",
    "            if self.isValid(s):\n",
    "                self.res.append(s)\n",
    "            return\n",
    "\n",
    "        for i in range(start, len(s)):\n",
    "            if i != 0 and s[i] == s[i-1]: continue\n",
    "            if r > 0 and s[i] == ')':\n",
    "                self.DFS(s[:i] + s[i+1:], i, l, r-1)\n",
    "            if l > 0 and s[i] == '(':\n",
    "                self.DFS(s[:i] + s[i+1:], i, l-1, r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        result = []\n",
    "        left = 0\n",
    "        right = 0\n",
    "        for c in s:\n",
    "            if c == \"(\":\n",
    "                left += 1\n",
    "            elif c == \")\":\n",
    "                if left > 0:\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    right += 1\n",
    "\n",
    "        def check(s):\n",
    "            l = 0\n",
    "            for c in s:\n",
    "                if c == \"(\":\n",
    "                    l += 1\n",
    "                elif c == \")\":\n",
    "                    l -= 1\n",
    "                    if l < 0:\n",
    "                        return False\n",
    "            return (l == 0)\n",
    "\n",
    "        def helper(s, k, l, r):\n",
    "            if l == 0 and r == 0:\n",
    "                if check(s):\n",
    "                    result.append(s)\n",
    "                return\n",
    "            for i in range(k, len(s)):\n",
    "                if i-1 >= k and s[i]==s[i-1]:\n",
    "                    continue\n",
    "                if s[i] == \"(\" and l > 0:\n",
    "                    helper(s[:i]+s[i+1:], i, l-1, r)\n",
    "                elif s[i] == \")\" and r > 0:\n",
    "                    helper(s[:i]+s[i+1:], i, l, r-1)\n",
    "        \n",
    "        helper(s, 0, left, right)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, string: str) -> List[str]:\n",
    "\n",
    "        self.res = []\n",
    "\n",
    "        # 统计右括号不匹配的数量放入r，左括号没有被匹配的数量放入l\n",
    "        # 这段感觉很不错\n",
    "        # 太哲学了，，，如果left > 0，那么还有挽回的余地，如果right > 0， 那么就没有挽回的余地\n",
    "        # 和做饭一样，盐放少了不怕，怕的是盐放多了（泪目\n",
    "        left = 0\n",
    "        right = 0\n",
    "\n",
    "        for char in string:\n",
    "            if char == '(':\n",
    "                left += 1\n",
    "            elif char == ')':\n",
    "                if left == 0:\n",
    "                    right += 1\n",
    "                else:\n",
    "                    left -= 1\n",
    "\n",
    "        # 验证目前的s中左右括号数目是否匹配\n",
    "        def _isValid(string):\n",
    "            count = 0\n",
    "            for char in string:\n",
    "                if char == '(':\n",
    "                    count += 1\n",
    "                if char == ')':\n",
    "                    count -= 1\n",
    "                if count < 0:\n",
    "                    return False  # ())))\n",
    "            return count == 0\n",
    "\n",
    "        # 回溯法\n",
    "        def dfs(string: str, start: int, left: int, right: int):\n",
    "            # 如果左右括号匹配，添加进结果集\n",
    "            if left == 0 and right == 0:\n",
    "                if _isValid(string):\n",
    "                    self.res.append(string)\n",
    "                return\n",
    "            # 如果左右不匹配\n",
    "            for i in range(start, len(string)):\n",
    "                # 如果i和前一个相同，那么删哪个结果都一样，故跳过\n",
    "                if i - 1 >= start and string[i] == string[i - 1]:\n",
    "                    continue\n",
    "                # 如果右括号有不匹配的，删去右括号，判断是否匹配\n",
    "                if right > 0 and string[i] == ')':\n",
    "                    dfs(string[:i] + string[i+1:], i, left, right-1)\n",
    "                # 如果左括号有不匹配的，删去左括号，判断是否匹配\n",
    "                if left > 0 and string[i] == '(':\n",
    "                    dfs(string[:i] + string[i+1:], i, left-1, right)\n",
    "\n",
    "        dfs(string, 0, left, right)\n",
    "        return self.res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    solution = Solution()\n",
    "    res = solution.removeInvalidParentheses('()())()')\n",
    "    print(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countInvalid(self,s:str):\n",
    "        # 收集不合法的left和right\n",
    "        left = 0\n",
    "        right = 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==\"(\":\n",
    "                left+=1\n",
    "            elif s[i]==\")\":\n",
    "                if left==0:\n",
    "                    right+=1\n",
    "                else:\n",
    "                    left-=1\n",
    "\n",
    "        return left,right\n",
    "    \n",
    "    def helper(self,s,start,l,r,res):\n",
    "        \n",
    "        if l==0 and r==0:\n",
    "            left,right = self.countInvalid(s)\n",
    "            if left==0 and right==0:\n",
    "                res.append(s)\n",
    "            return \n",
    "        for i in range(start,len(s)):\n",
    "            if i!=start and s[i]==s[i-1]:\n",
    "                continue\n",
    "            if s[i]==\")\" or s[i]==\"(\":\n",
    "                cur_s = s[:i]+s[i+1:]\n",
    "                if (r>0):\n",
    "                    self.helper(cur_s,i,l,r-1,res)\n",
    "                elif (l>0):\n",
    "                    self.helper(cur_s,i,l-1,r,res)\n",
    "\n",
    "\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        res = list()\n",
    "\n",
    "        if s==None or len(s)==0:\n",
    "            return [\"\"]\n",
    "        \n",
    "        left,right = self.countInvalid(s)\n",
    "        self.helper(s,0,left,right,res)\n",
    "     \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        invalid_left = invalid_right = 0\n",
    "        for char in s:\n",
    "            if char == '(':\n",
    "                invalid_left += 1\n",
    "            if char == ')':\n",
    "                if invalid_left > 0:\n",
    "                    invalid_left -= 1\n",
    "                else:\n",
    "                    invalid_right += 1\n",
    "\n",
    "        res = []\n",
    "        self.dfs(s, 0, invalid_left, invalid_right, res)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, string, pos, l, r, res):\n",
    "        if l == 0 and r == 0:\n",
    "            if self.is_valid(string):\n",
    "                res.append(string[:])\n",
    "            return\n",
    "\n",
    "        for i in range(pos, len(string)):\n",
    "            if i > pos and string[i] == string[i - 1]:\n",
    "                continue\n",
    "\n",
    "            if l > 0 and string[i] == '(':\n",
    "                self.dfs(string[:i] + string[i + 1:], i, l - 1, r, res)\n",
    "            if r > 0 and string[i] == ')':\n",
    "                self.dfs(string[:i] + string[i + 1:], i, l, r - 1, res)\n",
    "\n",
    "    def is_valid(self, string):\n",
    "        count = 0\n",
    "        for char in string:\n",
    "            if char == '(':\n",
    "                count += 1\n",
    "            if char == ')':\n",
    "                count -= 1\n",
    "            if count < 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        def is_valid(string):\n",
    "            count = 0\n",
    "            for char in string:\n",
    "                if char == \"(\": count += 1\n",
    "                elif char == \")\": count -= 1\n",
    "                if count < 0: return False\n",
    "            return count == 0\n",
    "\n",
    "        level = {s}\n",
    "        while True:\n",
    "            # level 中，选出满足的返回\n",
    "            valid = list(filter(is_valid,level))\n",
    "            if valid: return valid\n",
    "            # 如果不满足，单步差分\n",
    "            next_level = set()\n",
    "            for item in level:\n",
    "                for i in range(len(item)):\n",
    "                    if item[i] in \"()\": # 如果是一个括号\n",
    "                        next_level.add(item[:i]+item[i+1:])\n",
    "            # 将level中的字符串，每个位置都卸掉一个，存入level\n",
    "            level = next_level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "\n",
    "        def isValid(s:str)->bool:\n",
    "            cnt = 0\n",
    "            for c in s:\n",
    "                if c == \"(\": \n",
    "                    cnt += 1\n",
    "                elif c == \")\": \n",
    "                    cnt -= 1\n",
    "                if cnt < 0: \n",
    "                    return False  # 只用中途cnt出现了负值，你就要终止循环，已经出现非法字符了\n",
    "            return cnt == 0\n",
    "\n",
    "        # BFS\n",
    "        level = {s}  # 用set避免重复\n",
    "        while True:\n",
    "            valid = list(filter(isValid, level))  # 所有合法字符都筛选出来\n",
    "            if valid: \n",
    "                return valid # 如果当前valid是非空的，说明已经有合法的产生了\n",
    "            # 下一层level\n",
    "            next_level = set()\n",
    "            for item in level:\n",
    "                for i in range(len(item)):\n",
    "                    if item[i] in \"()\":                     # 如果item[i]这个char是个括号就删了，如果不是括号就留着\n",
    "                        next_level.add(item[:i]+item[i+1:])\n",
    "            level = next_level\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s):\n",
    "        def judge(s_target):\n",
    "            count = 0\n",
    "            for x in s_target:\n",
    "                if x == '(':\n",
    "                    count += 1\n",
    "                elif x == ')':\n",
    "                    count -= 1\n",
    "                if count < 0:\n",
    "                    return False\n",
    "            return count == 0\n",
    "        \n",
    "        res = set()\n",
    "        if judge(s):\n",
    "            res.add(s)\n",
    "            return list(res)\n",
    "        \n",
    "        queue = set([s])\n",
    "        while queue:\n",
    "            queue_tmp = set()\n",
    "            for node in queue:\n",
    "                for i in range(len(node)):\n",
    "                    if node[i] in ')(':\n",
    "                        tmp = node[:i] + node[i+1:]\n",
    "                        if len(tmp) > 0:\n",
    "                            if judge(tmp):\n",
    "                                res.add(tmp)\n",
    "                            else:\n",
    "                                queue_tmp.add(tmp)#this else will be a little nonstandard for the judge True level...\n",
    "            if res:\n",
    "                return list(res)\n",
    "            queue = queue_tmp\n",
    "        return [\"\"]\n",
    "                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        def isVaild(s: str) -> bool:\n",
    "            l, r = 0, 0\n",
    "            for c in s:\n",
    "                if c == \"(\":\n",
    "                    l += 1\n",
    "                elif c == \")\":\n",
    "                    r += 1\n",
    "                if r > l:\n",
    "                    return False\n",
    "            return l == r\n",
    "\n",
    "        level = {s}\n",
    "        while True:\n",
    "            vaild = list(filter(isVaild, level))\n",
    "            if vaild:\n",
    "                return vaild\n",
    "            next = set()\n",
    "            for item in level:\n",
    "                for i in range(len(item)):\n",
    "                    next.add(item[:i] + item[i + 1:])\n",
    "            level = next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        def isValid(s):\n",
    "            cnt = 0\n",
    "            for c in s:\n",
    "                if c == '(':\n",
    "                    cnt += 1\n",
    "                elif c == ')':\n",
    "                    cnt -= 1\n",
    "                    if cnt < 0: return False\n",
    "            return cnt == 0\n",
    "\n",
    "        if isValid(s): return [s]\n",
    "        q = [s]\n",
    "        res = []\n",
    "        while True:\n",
    "            new_q = []\n",
    "            while len(q) > 0:\n",
    "                cur_s = q.pop()\n",
    "                for i in range(len(cur_s)):\n",
    "                    if cur_s[i] != '(' and cur_s[i] != ')': continue\n",
    "                    new_s = cur_s[:i] + cur_s[i+1:]\n",
    "                    if isValid(new_s):\n",
    "                        res.append(new_s)\n",
    "                    new_q.append(new_s)\n",
    "            if len(res) > 0:\n",
    "                res = list(set(res))\n",
    "                return res\n",
    "            q = list(set(new_q))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        l = r = 0\n",
    "        st=set()\n",
    "        for et in s:\n",
    "            if et=='(':\n",
    "                l+=1\n",
    "            if et==')':\n",
    "                if l>0:\n",
    "                    l-=1\n",
    "                else:\n",
    "                    r+=1\n",
    "        def DFS(idx,lc,rc,l,r,str):\n",
    "            if idx==len(s):\n",
    "                if not l and not r:\n",
    "                    st.add(str)\n",
    "                return\n",
    "            if s[idx]=='(' and l:\n",
    "                DFS(idx+1,lc,rc,l-1,r,str)\n",
    "            if s[idx]==')' and r:\n",
    "                DFS(idx+1,lc,rc,l,r-1,str)\n",
    "            if s[idx] not in '()':\n",
    "                DFS(idx+1,lc,rc,l,r,str+s[idx])\n",
    "            if s[idx]=='(':\n",
    "                DFS(idx+1,lc+1,rc,l,r,str+'(')\n",
    "            if s[idx]==')' and lc>rc:\n",
    "                DFS(idx+1,lc,rc+1,l,r,str+')')\n",
    "            return\n",
    "        DFS(0,0,0,l,r,'')\n",
    "        return list(st)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        count = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                count += 1\n",
    "            elif c == ')':\n",
    "                count -= 1\n",
    "                if count < 0:\n",
    "                    return False\n",
    "        return count == 0\n",
    "    \n",
    "    def dfs(self, s: str, start: int, left: int, right: int, res: List[str]) -> None:\n",
    "        if left == 0 and right == 0:\n",
    "            if self.isValid(s):\n",
    "                res.append(s)\n",
    "            return\n",
    "        for i in range(start, len(s)):\n",
    "            if i != start and s[i] == s[i-1]:\n",
    "                continue\n",
    "            if s[i] == '(' and left > 0:\n",
    "                tmp = s[:i] + s[i+1:]\n",
    "                self.dfs(tmp, i, left-1, right, res)\n",
    "            if s[i] == ')' and right > 0:\n",
    "                tmp = s[:i] + s[i+1:]\n",
    "                self.dfs(tmp, i, left, right-1, res)\n",
    "    \n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        left = 0\n",
    "        right = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                left += 1\n",
    "            elif c == ')':\n",
    "                if left > 0:\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    right += 1\n",
    "        self.dfs(s, 0, left, right, res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from typing import *\n",
    "\n",
    "class Solution:\n",
    "    @ classmethod\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "\n",
    "        \n",
    "        def dfs(idx, cur_l, cur_r, delete_l, delete_r, path):\n",
    "            if idx == length:\n",
    "                if not delete_l and not delete_r:\n",
    "                    # delete_r 和 delete_l都为0， cur_l和cur_r一定相等\n",
    "                    if path not in ans:\n",
    "                        ans.append(path)\n",
    "                return\n",
    "            \n",
    "            #cur_r > cur_l说明有未配对右括号 \n",
    "            if delete_l < 0 or delete_r < 0 or cur_r > cur_l:\n",
    "                return\n",
    "            \n",
    "            ss = s[idx]\n",
    "            if ss == '(':\n",
    "                dfs(idx+1, cur_l, cur_r, delete_l-1, delete_r, path) #删去ss\n",
    "            elif ss == ')':\n",
    "                dfs(idx+1, cur_l, cur_r, delete_l, delete_r-1, path) #删去ss\n",
    "            dfs(idx+1, cur_l+(ss=='('), cur_r+(ss==')'), delete_l, delete_r, path+ss)\n",
    "\n",
    "\n",
    "        ans = []\n",
    "        length = len(s)\n",
    "\n",
    "        l = r = 0\n",
    "        for ss in s:\n",
    "            if ss == '(':\n",
    "                l += 1\n",
    "            elif ss == ')':\n",
    "                if l:\n",
    "                    l -= 1\n",
    "                else:\n",
    "                    r += 1\n",
    "        # 得到有l个左括号，r个右括号无法配对\n",
    "\n",
    "        dfs(0, 0, 0, l, r, \"\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "\n",
    "        def isValid(s):\n",
    "            lremove = rremove = 0\n",
    "            for i in range(len(s)):\n",
    "                if s[i] == '(':\n",
    "                    lremove += 1\n",
    "                elif s[i] == ')':\n",
    "                    if lremove > 0:\n",
    "                        lremove -= 1\n",
    "                    else:\n",
    "                        rremove += 1\n",
    "            return lremove, rremove, lremove == 0 and rremove == 0\n",
    "        lremove, rremove, _ = isValid(s)\n",
    "        def helper(s, start, lremove, rremove):\n",
    "            if lremove == 0 and rremove == 0:\n",
    "                _, _, st = isValid(s)\n",
    "                if st:\n",
    "                    res.append(s)\n",
    "                    return\n",
    "            for i in range(start, len(s)):\n",
    "                if i > start and s[i] == s[i-1]:    # 防止重复\n",
    "                    continue\n",
    "                if lremove + rremove > len(s) - i:  # 剪枝\n",
    "                    break\n",
    "                if lremove >0 and s[i] == '(':\n",
    "                    helper(s[:i]+s[i+1:], i, lremove-1, rremove)\n",
    "                if rremove >0 and s[i] == ')':\n",
    "                    helper(s[:i]+s[i+1:], i, lremove, rremove-1)\n",
    "        \n",
    "        helper(s, 0, lremove, rremove)\n",
    "        return res\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/remove-invalid-parentheses/solution/bfsjian-dan-er-you-xiang-xi-de-pythonjiang-jie-by-\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        \n",
    "        def idValid(s):\n",
    "            n = 0\n",
    "            for c in s:\n",
    "                if c == \"(\":\n",
    "                    n += 1\n",
    "                elif c == \")\":\n",
    "                    n -= 1\n",
    "                if n < 0:\n",
    "                    return False\n",
    "            return n == 0\n",
    "        \n",
    "        cur = set([s])\n",
    "        while cur:\n",
    "            ans = list(filter(idValid, cur))\n",
    "            if ans:\n",
    "                return ans\n",
    "            \n",
    "            tmp = set()\n",
    "            for s in cur:\n",
    "                for i in range(len(s)):\n",
    "                    if s[i] in \"()\":\n",
    "                        tmp.add(s[:i] + s[i + 1:])\n",
    "            cur = tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        ans = set()\n",
    "        lremove = rremove = 0  # 提前计算出需要删除的左右括号数目\n",
    "        path = list(s)\n",
    "        for e in s:\n",
    "            if e == '(':\n",
    "                lremove += 1\n",
    "            elif e == ')': # 注意：含有字母，不能直接用else\n",
    "                if lremove > 0: lremove -= 1\n",
    "                else:\n",
    "                    rremove += 1\n",
    "        def isValid(s):  # 判断字符串是否合法\n",
    "            cnt = 0\n",
    "            for e in s:\n",
    "                if e == '(': cnt += 1\n",
    "                elif e == ')':\n",
    "                    cnt -= 1\n",
    "                    if cnt < 0: return False\n",
    "            return cnt == 0\n",
    "        def dfs(i, lremove, rremove):\n",
    "            if lremove == 0 and rremove == 0:\n",
    "                seq = ''.join(path)\n",
    "                if isValid(seq):\n",
    "                    ans.add(seq)\n",
    "                return\n",
    "            if i == len(s):\n",
    "                return\n",
    "            if s[i] == '(' and lremove > 0:\n",
    "                path[i] = ''\n",
    "                dfs(i + 1, lremove - 1, rremove)\n",
    "                path[i] = '('\n",
    "            if s[i] == ')' and rremove > 0:\n",
    "                path[i] = ''\n",
    "                dfs(i + 1, lremove, rremove - 1)\n",
    "                path[i] = ')'\n",
    "                \n",
    "            dfs(i + 1, lremove, rremove)\n",
    "\n",
    "        dfs(0, lremove, rremove)\n",
    "        return list(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        ans = set()\n",
    "        lremove = rremove = 0  # 提前计算出需要删除的左右括号数目\n",
    "        path = list(s)\n",
    "        for e in s:\n",
    "            if e == '(':\n",
    "                lremove += 1\n",
    "            elif e == ')': # 注意：含有字母，不能直接用else\n",
    "                if lremove > 0: lremove -= 1\n",
    "                else:\n",
    "                    rremove += 1\n",
    "        def isValid(s):  # 判断字符串是否合法\n",
    "            cnt = 0\n",
    "            for e in s:\n",
    "                if e == '(': cnt += 1\n",
    "                elif e == ')':\n",
    "                    cnt -= 1\n",
    "                    if cnt < 0: return False\n",
    "            return cnt == 0\n",
    "        def dfs(i, lremove, rremove):\n",
    "            if lremove == 0 and rremove == 0:\n",
    "                seq = ''.join(path)\n",
    "                if isValid(seq):\n",
    "                    ans.add(seq)\n",
    "                return\n",
    "            if i == len(s):\n",
    "                return\n",
    "            if s[i] == '(' and lremove > 0:\n",
    "                path[i] = ''\n",
    "                dfs(i + 1, lremove - 1, rremove)\n",
    "                path[i] = '('\n",
    "            if s[i] == ')' and rremove > 0:\n",
    "                path[i] = ''\n",
    "                dfs(i + 1, lremove, rremove - 1)\n",
    "                path[i] = ')'\n",
    "\n",
    "            dfs(i + 1, lremove, rremove)\n",
    "\n",
    "        dfs(0, lremove, rremove)\n",
    "        return list(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        n=len(s)\n",
    "        index=0\n",
    "        r1,r2=0,0\n",
    "        indexls=[0 for i in range(n)]\n",
    "        sum1=sum(int(i in [\"(\",\")\"]) for i in s)\n",
    "        for i in range(n):\n",
    "            if s[i]==\"(\":\n",
    "                index-=1\n",
    "            elif s[i]==\")\":\n",
    "                index+=1\n",
    "            if index>0:\n",
    "                r1+=1\n",
    "                index-=1\n",
    "            indexls[i]=index\n",
    "        if index<0:\n",
    "            r2=-index\n",
    "        target=sum1-r1-r2\n",
    "        targettotal=n-r1-r2\n",
    "\n",
    "        path=[[],[0]]\n",
    "        result=[]\n",
    "        dic={}\n",
    "        def dfs(i):\n",
    "\n",
    "            if len(path[0])>=targettotal and path[1][-1]==0 and (\"\".join(path[0][:] )not in dic):\n",
    "                result.append(\"\".join(path[0][:]))\n",
    "                dic[\"\".join(path[0][:])]=1\n",
    "                return\n",
    "            else:\n",
    "                for j in range(i,min(n-(targettotal-len(path[0]))+1,n)):\n",
    "                    \n",
    "                    if s[j] not in [\"(\",\")\"]:\n",
    "                        path[0].append(s[j])\n",
    "                        dfs(j+1)\n",
    "                        path[0].pop()\n",
    "                        break\n",
    "                    elif s[j]==\"(\":\n",
    "                        path[0].append(s[j])\n",
    "                        path[1][0]-=1\n",
    "                        dfs(j+1)\n",
    "                        path[1][0]+=1\n",
    "                        path[0].pop()\n",
    "                    elif s[j]==\")\" and path[1][-1]<0:\n",
    "                        path[0].append(s[j])\n",
    "                        path[1][0]+=1\n",
    "                        dfs(j + 1)\n",
    "                        path[0].pop()\n",
    "                        path[1][0]-=1\n",
    "        dfs(0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        index = 0\n",
    "        r1, r2 = 0, 0\n",
    "        indexls = [0 for i in range(n)]\n",
    "        sum1 = sum(int(i in [\"(\", \")\"]) for i in s)\n",
    "        for i in range(n):\n",
    "            if s[i] == \"(\":\n",
    "                index -= 1\n",
    "            elif s[i] == \")\":\n",
    "                index += 1\n",
    "            if index > 0:\n",
    "                r1 += 1\n",
    "                index -= 1\n",
    "            indexls[i] = index\n",
    "        if index < 0:\n",
    "            r2 = -index\n",
    "        target = sum1 - r1 - r2\n",
    "        targettotal = n - r1 - r2\n",
    "\n",
    "        path = [[], [0]]\n",
    "        result = []\n",
    "        dic = {}\n",
    "        def dfs(i):\n",
    "            if len(path[0]) >= targettotal and path[1][-1] == 0 and (\"\".join(path[0][:]) not in dic):\n",
    "                result.append(\"\".join(path[0][:]))\n",
    "                dic[\"\".join(path[0][:])] = 1\n",
    "                return\n",
    "            if i>=n:\n",
    "                return\n",
    "            else:\n",
    "\n",
    "                if s[i] not in [\"(\", \")\"]:\n",
    "                        path[0].append(s[i])\n",
    "                        dfs(i + 1)\n",
    "                        path[0].pop()\n",
    "                elif s[i] == \"(\":\n",
    "                    path[0].append(s[i])\n",
    "                    path[1][0] -= 1\n",
    "                    dfs(i + 1)\n",
    "                    path[1][0] += 1\n",
    "                    path[0].pop()\n",
    "                    dfs(i+1)\n",
    "                elif s[i] == \")\" and path[1][-1] < 0:\n",
    "                    path[0].append(s[i])\n",
    "                    path[1][0] += 1\n",
    "                    dfs(i + 1)\n",
    "                    path[0].pop()\n",
    "                    path[1][0] -= 1\n",
    "                    dfs(i+1)\n",
    "                elif s[i]==\")\" and path[1][-1]>=0:\n",
    "                    dfs(i+1)\n",
    "\n",
    "        dfs(0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        lens = len(s)\n",
    "        \n",
    "        l = r = 0\n",
    "        # get parathesis to be removed for both left and right\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                l += 1\n",
    "            elif c == ')':\n",
    "                if l:\n",
    "                    l -= 1\n",
    "                else:\n",
    "                    r += 1\n",
    "        \n",
    "\n",
    "        res = []\n",
    "        # idx：当前字符的索引\n",
    "        # cl：保留的左括号数量\n",
    "        # cr：保留的右括号数量\n",
    "        # dl：需要移除的左括号数量\n",
    "        # dr：需要移除的右括号数量\n",
    "        # path：保留下来的字符串\n",
    "\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, cl, cr, dl, dr, path):\n",
    "            if idx == lens:\n",
    "                if not dl and not dr:\n",
    "                    res.append(path)\n",
    "                return \n",
    "\n",
    "            # 若当前保留的右括号大于左括号，那必然不合法了\n",
    "            # 移除的左括号，右括号超出了，那不行\n",
    "            if cr>cl or dl<0 or dr<0:\n",
    "                return \n",
    "\n",
    "            c = s[idx]\n",
    "\n",
    "            # 移除'('，dfs下去看看行不行\n",
    "            if c == '(':\n",
    "                dfs(idx+1, cl, cr, dl-1, dr, path)\n",
    "            # 移除')'，dfs下去看看行不行\n",
    "            elif c == ')':\n",
    "                dfs(idx+1, cl, cr, dl, dr-1, path)\n",
    "            \n",
    "            # '(', ')', 小写字母均不删除\n",
    "            dfs(idx+1, cl+(c=='('), cr+(c==')'), dl, dr, path+c)\n",
    "\n",
    "\n",
    "        dfs(0, 0, 0, l, r, '')\n",
    "\n",
    "        # 如果不想最后去重，可在dfs前加记忆话搜索：@lru_cache(None)\n",
    "        # return list(set(res))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        l = r = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                l += 1\n",
    "            elif c == ')':\n",
    "                if l:\n",
    "                    l -= 1\n",
    "                else:\n",
    "                    r += 1\n",
    "        ans = []\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, cl, cr, dl, dr, path):\n",
    "            if idx == len(s):\n",
    "                if not dl and not dr:\n",
    "                    ans.append(path)\n",
    "                return\n",
    "            if cr > cl or dl < 0 or dr < 0:\n",
    "                return\n",
    "            c = s[idx]\n",
    "            if c == '(':\n",
    "                dfs(idx+1,cl,cr,dl-1,dr, path)\n",
    "            elif c == ')':\n",
    "                dfs(idx+1,cl,cr,dl,dr-1, path)\n",
    "            dfs(idx+1,cl+(c=='('),cr+(c==')'),dl,dr, path+c)\n",
    "        \n",
    "        dfs(0, 0, 0, l, r, \"\")\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str):\n",
    "        def isValid(s: str) -> bool:\n",
    "            count = 0\n",
    "            for ch in s:\n",
    "                if ch == '(':\n",
    "                    count += 1\n",
    "                elif ch == ')':\n",
    "                    if count == 0:\n",
    "                        return False\n",
    "                    count -= 1\n",
    "            return count == 0\n",
    "\n",
    "        level = {s}\n",
    "        while True:\n",
    "            valid = list(filter(isValid, level))\n",
    "            if valid:\n",
    "                return valid\n",
    "            level = {s[:i] + s[i + 1:] for s in level for i in range(len(s))}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        def is_valid(s):\n",
    "            need_right = 0\n",
    "            for c in s:\n",
    "                if c=='(':\n",
    "                    need_right += 1\n",
    "                elif c==')':\n",
    "                    need_right -= 1\n",
    "                    if need_right<0:\n",
    "                        return False\n",
    "            return need_right==0\n",
    "        \n",
    "        q = deque()\n",
    "        visited = set()\n",
    "\n",
    "        q.append(s)\n",
    "        visited.add(s)\n",
    "        while len(q)>0:\n",
    "            N = len(q)\n",
    "            res = []\n",
    "            for _ in range(N):\n",
    "                cur = q.popleft()\n",
    "                if is_valid(cur):\n",
    "                    res.append(cur)\n",
    "                else:\n",
    "                    for k in range(len(cur)):\n",
    "                        if cur[k] in ['(', ')']:\n",
    "                            delete_res = cur[:k] + cur[k+1:]\n",
    "                            if delete_res not in visited:\n",
    "                                q.append(delete_res)\n",
    "                                visited.add(delete_res)\n",
    "            if len(res)>0:\n",
    "                return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        def check(ss):\n",
    "            cnt = 0\n",
    "            for x in ss:\n",
    "                if x == '(':\n",
    "                    cnt += 1\n",
    "                elif x == ')':\n",
    "                    cnt -= 1\n",
    "                if cnt < 0:\n",
    "                    return False\n",
    "            return cnt == 0\n",
    "        \n",
    "        level = set()\n",
    "        level.add(s)\n",
    "\n",
    "        while True:\n",
    "            valid = []\n",
    "            print(level)\n",
    "            for x in level:\n",
    "                if check(x):\n",
    "                    valid.append(x)\n",
    "            if valid:\n",
    "                return valid\n",
    "\n",
    "            nlevel = []\n",
    "            for x in level:\n",
    "                for i in range(len(x)):\n",
    "                    if x[i] in '()':\n",
    "                        nlevel.append(x[:i] + x[i + 1:])\n",
    "            level = set(nlevel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        def valid(s):\n",
    "            t = 0\n",
    "            for c in s:\n",
    "                if c == \"(\":\n",
    "                    t += 1\n",
    "                elif c == \")\":\n",
    "                    t -= 1\n",
    "                if t < 0:\n",
    "                    return False\n",
    "            return t == 0\n",
    "            \n",
    "        if valid(s):\n",
    "            return[s]\n",
    "\n",
    "        seen = set()\n",
    "        res = set()\n",
    "        q = deque([s])\n",
    "        cnt = 0\n",
    "        while not res:\n",
    "            l = len(q)\n",
    "            for _ in range(l):\n",
    "                curr = q.popleft()\n",
    "                for j in range(len(curr)):\n",
    "                    new_s = curr[:j] + curr[j+1:]\n",
    "                    if valid(new_s):\n",
    "                        found = True\n",
    "                        res.add(new_s)\n",
    "                    elif new_s not in seen:\n",
    "                        q.append(new_s)\n",
    "                        seen.add(new_s)\n",
    "        return list(res)\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str) -> List[str]:\n",
    "        result=[]\n",
    "        def validate(lst):\n",
    "            count=0\n",
    "            for i in range(len(lst)):\n",
    "                if lst[i]=='(':\n",
    "                    count+=1\n",
    "                elif lst[i]==')':\n",
    "                    count-=1\n",
    "                    if count<0:\n",
    "                        return False\n",
    "            return True if count==0 else False\n",
    "        result=[]\n",
    "        if validate(s):\n",
    "            return [s]\n",
    "        \n",
    "        queue=deque([s])\n",
    "        dic={s:True}\n",
    "        while True:\n",
    "            new_queue=deque()\n",
    "            while queue:\n",
    "                word=queue.popleft()\n",
    "                for i in range(len(word)):\n",
    "                    new_s=word[:i]+word[i+1:]\n",
    "                    if validate(new_s):\n",
    "                        result.append(new_s)\n",
    "                    else:\n",
    "                        if new_s not in dic and new_s not in result:\n",
    "                            new_queue.append(new_s)\n",
    "                            dic[new_s]=True\n",
    "            queue=new_queue\n",
    "            if len(result)>0:\n",
    "                break\n",
    "        result=set(result)\n",
    "        return list(result)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
